package oj;

//翻转二叉树：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
public class Solution_226 {
    //用中序的方式来解决
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        //先处理左子树
        invertTree(root.left);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //此处不是 root.right 是因为根结点的左子树已经发生了翻转，并且与 tmp 和 root.right 进行了交换
        //所以这里的 root.right 本质上还是 root.left 所以会发生错误
        invertTree(root.left);
        return root;
    }

    //用前序的方式来解决
//    public TreeNode invertTree(TreeNode root){
//        if(root == null){
//            return null;
//        }
//        //先进行交换
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        //继续处理左右子树
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
//    }

    //用后序的方式解决
//    public TreeNode invertTree(TreeNode root){
//        if(root == null){
//            return null;
//        }
//        //先对左右子树进行递归
//        invertTree(root.left);
//        invertTree(root.right);
//        //再进行交换
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        return root;
//    }
}
